public class Leetcode {
}
//leetcode:494:目标和
class Solution1 {
    //a+b = sum;
    //a-b = target
    //a = (sum+target)/2
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0 , n = nums.length;
        for(int x : nums) sum += x;
        int aim = (sum + target) / 2;
        if(aim < 0 || (sum + target) % 2 == 1) return 0;

        //创建一个dp表，表示从前i个数选，总和正好等于j一共有多少种选法
        int[][] dp = new int[n+1][aim+1];
        dp[0][0] = 1;

        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= aim; j++){
                //不选i位置
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1])
                    //选i位置和不选i位置的总和即为前i个数选，总和正好等于j的选法个数
                    dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][aim];
    }
}

//滚动数组优化
class Solution2 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0 , n = nums.length;
        for(int x : nums) sum += x;
        int aim = (sum + target) / 2;
        if(aim < 0 || (sum + target) % 2 == 1) return 0;

        int[] dp = new int[aim+1];
        dp[0] = 1;

        for(int i = 1; i <= n; i++){
            for(int j = aim; j >= nums[i-1]; j--){
                dp[j] += dp[j-nums[i-1]];
            }
        }
        return dp[aim];
    }
}

//leetcode:1049:最后一块石头的重量II
class Solution3 {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length , sum = 0;
        for(int x : stones) sum += x;

        //如果组合成的数越接近一半，那么此时剩下的重量将会最小
        int aim = sum / 2;

        //创建一个dp表，表示，从前i个数中选，总和不超过j的，最大和
        int[][] dp = new int[n+1][aim+1];

        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= aim; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= stones[i-1])
                    dp[i][j] = Math.max(dp[i][j] , dp[i-1][j-stones[i-1]] + stones[i-1]);
            }
        }
        return sum - 2*dp[n][aim];
    }
}

//滚动数组优化
class Solution4 {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length , sum = 0;
        for(int x : stones) sum += x;

        int aim = sum / 2;

        int[] dp = new int[aim+1];

        for(int i = 1; i <= n; i++){
            for(int j = aim; j >= stones[i-1]; j--){
                dp[j] = Math.max(dp[j] , dp[j-stones[i-1]] + stones[i-1]);
            }
        }
        return sum - 2*dp[aim];
    }
}